package com.huangpeng.algorithm.dijestra;

import java.util.Arrays;

/**
 * @Author hp
 * @Title 创建图类
 * @Package
 * @Date 2021/12/31 16:14
 * @Description
 * @Version 1.0
 */
public class Graph {
    private char[] vertex;//顶点字符数组
    private int[][] arr;
    private VisitedVertex vv;//已访问的节点集合

    public Graph(char[] vertex, int[][] arr) {
        this.vertex = vertex;
        this.arr = arr;
    }

    public void show(){
        for (int[] link : arr) {
            System.out.println(Arrays.toString(link));
        }
    }

    public void djk(int index){
        vv = new VisitedVertex(vertex.length,index);
        update(index);
        for (int i = 1; i < vertex.length; i++) {
            index = vv.updateArr();
            update(index);
        }
    }

    /**
     * 更新下标顶点到周围顶点的距离和周围顶点的前驱结点
     * @param index
     */
    private void update(int index) {
        int len = 0;//更新下标顶点到周围顶点的距离和周围顶点的前驱结点
        //遍历邻接矩阵
        for (int i = 0; i < arr[index].length; i++) {
            len = vv.getDis(index) + arr[index][i];
            //节点未被访问且节点距离有更小的值
            if(!vv.in(i) && len < vv.getDis(i)){
                vv.updatePre(i,index);
                vv.updateDis(i,len);
            }
        }
    }

    public void djkShow(){
        vv.showArr();
    }
}
